package com.lfg.leetcode.leetcode0;


/**
 * Given a string, find the length of the longest substring without repeating characters.
 * Examples:
 * Given "abcabcbb", the answer is "abc", which the length is 3.
 * Given "bbbbb", the answer is "b", with the length of 1.
 * Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequenceand not a substring.
 */


public class No3SubString {

    public static int LongestSubString(String content, String str) {
        for (int i = 0; i < content.length(); i++) {
            int m = i;
            for (int n = 0; n < str.length(); n++) {
                if (content.charAt(m) != str.charAt(n)) {
                    break;
                }
                m++;
                if (n == str.length() - 1) {
                    return n + 1;
                }
            }
        }
        return 0;
    }


    public static int kmp(String content, String str) {
        int[] next = getNext(str);
        int m = 0;
        for (int i = 0; i < content.length() && m < str.length(); i++) {
            if (content.charAt(i) != str.charAt(m)) {
                m = next[++m];
                continue;
            }
            m++;
            if (m == str.length()) {
                return m;
            }
        }
        return 0;
    }


    public static int[] getNext(String ps) {
        char[] data = ps.toCharArray();
        int[] ret = new int[data.length];
        int p = 0;
        int i = 1;
        ret[0] = -1;
        while (p < data.length) {
            if (data[i++] == data[p++]) {
                ret[p] = ret[p - 1] + 1;
            } else {
                i = ret[i];//不符合的话要回溯
            }
        }

        return ret;
    }

    public static void main(String[] args) {

        int[] ret = getNext("ab1ca1ab1c1d");
        System.out.println(kmp("aabbccabc", "abc"));
    }
}
